package com.demo.java.OD401_450.OD446;

import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【分披萨(C&D卷-200分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146327578
 */
public class OdMain {
    private static int n;
    private static int[] nums;
    private static int[][] mem;

    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in)) {
            // 读取输入的数字和大小
            n = sc.nextInt();
            nums = new int[n];
            mem = new int[n][n]; // 备忘录

            // 读取每个数字，存入 nums 数组
            for (int i = 0; i < n; i++) {
                nums[i] = sc.nextInt();
            }

            int result = 0; // 初始化结果为 0
            // 遍历每个位置，尝试从每个位置开始选择
            for (int i = 0; i < n; i++) {
                int left = (i + n + 1) % n;  // 左边的指针
                int right = (i + n - 1) % n; // 右边的指针
                int target = bfs(left, right); // 调用递归函数来获取最优解
                if (target + nums[i] > result) {
                    result = target + nums[i]; // 计算最大结果
                }
            }

            // 输出最终的最大分数
            System.out.println(result);
        }
    }

    // 使用备忘录和递归的方式计算最优选择
    private static int bfs(int left, int right) {
        if (nums[left] > nums[right]) {
            left = (left + n + 1) % n;  // 如果左边的块较大，则选择左边
        } else if (nums[left] < nums[right]) {
            right = (right + n - 1) % n; // 如果右边的块较大，则选择右边
        }

        // 通过备忘录避免重复计算
        if (mem[left][right] <= 0) {
            if (left == right) {  // 如果剩下的就是一个块
                mem[left][right] = nums[left];  // 返回该块的大小
            } else {
                int newLeft = (left + 1) % n; // 吃左边的块
                int newRight = (right + n - 1) % n; // 吃右边的块
                mem[left][right] = nums[left] + bfs(newLeft, right); // 吃左边块的结果
                int rightValue = nums[right] + bfs(left, newRight); // 吃右边块的结果
                if (rightValue > mem[left][right]) {
                    mem[left][right] = rightValue; // 选择更优的结果
                }
            }
            return mem[left][right];  // 返回当前选择的最大分数
        } else {
            return mem[left][right];  // 如果已经计算过，直接返回备忘录中的值
        }
    }
}
